package acwing._2LanQiao._1Recursion;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing._2LanQiao._1_1Recursion
 * @File : Q0095.java
 * @Author : WangRuoyu
 * @Date : 2023/3/13 10:48
 */

public class Q0095 {

    public static void turn(int[][] d, int x, int y) {
        d[x][y] = 1 - d[x][y];
        if (x > 0) {
            d[x - 1][y] = 1 - d[x - 1][y];
        }
        if (x < 4) {
            d[x + 1][y] = 1 - d[x + 1][y];
        }
        if (y > 0) {
            d[x][y - 1] = 1 - d[x][y - 1];
        }
        if (y < 4) {
            d[x][y + 1] = 1 - d[x][y + 1];
        }
    }

    static boolean check(int[][] d) {
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                if (d[i][j] == 0) return false;
            }
        }
        return true;
    }

    static void printd(int[][] d) {
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 5; ++j) {
                System.out.print(d[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    static int dfs(int[][] d, int k, int res) {
        if (k > 4) {
            if (check(d)) {
                return res;
            }
            return -1;
        }
        for (int i = 0; i < 5; ++i) {
            if (d[k - 1][i] == 0) {
                turn(d, k, i);
                res++;
            }
        }
        return dfs(d, k + 1, res);
    }

    public static void main(String[] args) {
        int[][] d;
        int res = 10;
        for (int i = 0; i < 32; ++i) {
            int step = 0;
            d = new int[][]{{0, 0, 1, 1, 1}, {0, 1, 0, 1, 1}, {1, 0, 0, 0, 1}, {1, 1, 0, 1, 0}, {1, 1, 1, 0, 0}};
//            d = new int[][]{{1, 1, 1, 0, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
//            d = new int[][]{{0, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}};
            for (int j = 0; j < 5; ++j) {
                if ((i >> j & 1) == 1) {
                    turn(d, 0, 4 - j);
                    step++;
                }
            }
            if (check(d)) {
                System.out.println(step);
                return;
            }
            int tmp = dfs(d, 1, step);
            if (tmp != -1) {
                res = Math.min(res, tmp);
            }
        }
        if (res != 10) {
            System.out.println(res);
        } else {
            System.out.println(-1);
        }
    }
}
